﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Text.RegularExpressions;

namespace OtomatSearching.Engine
{
    public class OtomatSearch
    {
        private int[] m_int_next;
        private int m_int_violate;  // Lỗi vi phạm
        private int m_int_threshold;
        private int m_int_position;
        /// <summary>
        /// Ngưỡng phạt của Otomat
        /// </summary>
        public int Threshold
        {
            get { return m_int_threshold; }
            set { m_int_threshold = value; }
        }
        /// <summary>
        /// Lỗi phạm phải
        /// </summary>
        public int Violate
        {
            get { return m_int_violate; }
        }

        public int Position
        {
            get { return m_int_position; }
        }

        public int Length
        {
            get { return m_int_next.Length + m_int_violate; }
        }
        // Nhảy tới vị trí tìm tiếp theo trong đoạn văn bản
        public int Next
        {
            get { return m_int_position + m_int_next.Length + m_int_violate; }
        }

        public OtomatSearch()
        {
            this.m_int_threshold = 4;
            this.m_int_position = 0;    // Mặc định ban đầu là 0
            this.m_int_violate = 0;
            this.m_int_next = new int[0];
        }

        public OtomatSearch(int ip_int_threshold)
            : this()
        {
            this.m_int_threshold = ip_int_threshold;
        }

        private void CreateNextTable(string ip_str_pattern)
        {
            var plen = ip_str_pattern.Length;
            if (plen <= 1)
            {
                this.m_int_next = new int[plen];
                this.m_int_next[0] = -1;
                return;
            }
            var v_int_pos = 2;
            var v_int_cnd = 0;
            // Default assign
            this.m_int_next = new int[plen];
            this.m_int_next[0] = -1;
            this.m_int_next[1] = 0;
            while (v_int_pos < plen)
            {
                if (Char.ToUpper(ip_str_pattern[v_int_pos - 1]) == Char.ToUpper(ip_str_pattern[v_int_cnd]))
                {
                    this.m_int_next[v_int_pos] = v_int_cnd + 1;
                    v_int_pos++;
                    v_int_cnd++;
                }
                else if (v_int_cnd > 0)
                {
                    v_int_cnd = this.m_int_next[v_int_cnd];
                }
                else
                {
                    this.m_int_next[v_int_pos] = 0;
                    v_int_pos++;
                }
            }
        }
        /// <summary>
        /// Tìm kiếm theo tiếp cận Otomat
        /// </summary>
        /// <param name="ip_str_corpus">Văn bản tìm</param>
        /// <param name="ip_str_pattern">Mẫu</param>
        /// <returns></returns>
        public List<Oresult> Osearch(string ip_str_corpus, string ip_str_pattern, int ip_int_startIndex, bool ip_sapproximate)
        {
            if (ip_int_startIndex < 0)
            {
                throw new Exception("Index must be greater than zero");
            }
            var v_str_patterns = new string[0];
            var v_str_postfix = BalanHelper.Infix2Postfix(ip_str_pattern, out v_str_patterns);
            var list = new List<Oresult>();
            var osearch = ip_sapproximate == true ?
                new SearchHandler(SearchApproximate) :
                new SearchHandler(SearchAccurate);
            var stack = new Stack<bool>();
            var hashtable = new Hashtable();

            for (int i = 0; i < v_str_patterns.Length; i++)
            {
                //var next = this.Next > 0 ? this.Next : ip_int_startIndex;
                while (this.Next < ip_str_corpus.Length)
                {
                    var oresult = new Oresult();
                    oresult.Postion = osearch(ip_str_corpus, v_str_patterns[i], this.Next);
                    oresult.Length = this.Length;
                    list.Add(oresult);
                    hashtable[v_str_patterns[i]] = oresult;
                }
            }


            for (int i = 0; i < v_str_postfix.Length; i++)
            {
                var s = v_str_postfix[i];
                if (BalanHelper.IsOperand(s) == true)
                {
                    var oresult = (Oresult)hashtable[s];
                    stack.Push(oresult.Found);
                }
                else
                {
                    var right = stack.Pop();
                    var left = stack.Pop();
                    var result = Calculate(left, right, s);
                    stack.Push(result);
                }
            }
            if (stack.Count > 0 && stack.Pop() == false)
            {
                throw new Exception("Pattern not found to end");
            }
            return list;
        }

        /// Tìm kiếm theo tiếp cận Otomat
        /// </summary>
        /// <param name="ip_str_corpus">Văn bản tìm</param>
        /// <param name="ip_str_pattern">Mẫu</param>
        /// <returns></returns>
        public List<Oresult> Search(string ip_str_corpus, string ip_str_pattern, bool ip_sapproximate)
        {
            var list = new List<Oresult>();
            var osearch = ip_sapproximate == true ?
                new SearchHandler(SearchApproximate) :
                new SearchHandler(SearchAccurate);
            var stack = new Stack<bool>();
            var hashtable = new Hashtable();

            while (this.Next < ip_str_corpus.Length)
            {
                var oresult = new Oresult();
                oresult.Postion = osearch(ip_str_corpus, ip_str_pattern, this.Next);
                oresult.Length = this.Length;
                if (!oresult.Found)
                {
                    break;
                }
                list.Add(oresult);
            }

            return list;
        }


        private bool Calculate(bool left, bool right, string operatorr)
        {
            switch (operatorr)
            {
                case "-": return left && !right;
                case "+": return left && right;
                case "|": return left || right;
                case "%": return left && right;
            }
            return false;
        }

        private delegate int SearchHandler(string ip_str_sinput, string ip_str_pattern, int ip_int_startIndex);

        public int SearchApproximate(string ip_str_corpus, string ip_str_pattern, int ip_int_startIndex)
        {
            this.m_int_position = -1;
            this.m_int_violate = int.MaxValue;
            var v_int_violate = 0;
            var v_int_startIndex_backup = 0; // Backup position, khôi phục lại position của chuỗi, nếu không tìm thấy
            var plen = ip_str_pattern.Length;
            var slen = ip_str_corpus.Length;
            // Create next table
            this.CreateNextTable(ip_str_pattern);

            var k = 0;
            var j = 0;  // chỉ số trên mẫu p
            var i = 0;  // chỉ số tại th.điểm xảy ra ko khớp
            var m = ip_int_startIndex;
            var pattern = ip_str_pattern.ToUpper();
            while ((k = m + j + v_int_violate) < slen)
            {
                var sk = Char.ToUpper(ip_str_corpus[k]);
                if (sk == pattern[j])
                {
                    if (++j == plen)
                    {
                        if (v_int_violate == 0)
                        {
                            this.m_int_violate = 0;
                            this.m_int_position = m;
                            break;
                        }
                        else if (v_int_violate < this.m_int_violate)
                        {
                            this.m_int_violate = v_int_violate;
                            this.m_int_position = m;
                        }
                        // Tiếp tục tìm mới để được lỗi là nhỏ nhất
                        m += i - this.m_int_next[i];
                        j = this.m_int_next[i] > -1 ? this.m_int_next[i] : 0;
                        v_int_violate = 0; // reset
                    }
                }
                else if ((j + 1 < plen) && sk == pattern[j + 1])
                {
                    // TH này coi như ko phạm lỗi
                    if (++j == plen - 1)
                    {
                        // Lỗi phạm ít nhất 1 lỗi --> nên ko cần xét trường hợp (v_int_violate == this.m_int_violate
                        if (v_int_violate < this.m_int_violate)
                        {
                            this.m_int_violate = v_int_violate;
                            this.m_int_position = m;
                        }
                        // Tiếp tục tìm mới để được lỗi là nhỏ nhất
                        m += i - this.m_int_next[i];
                        j = this.m_int_next[i] > -1 ? this.m_int_next[i] : 0;
                        v_int_violate = 0; // reset
                    }
                }
                else
                {
                    // Mistakes or mismatches
                    v_int_violate++;
                    // Search new if violate exceeds m_int_threshold(4)
                    if (v_int_violate > m_int_threshold)
                    {
                        m += i - this.m_int_next[i];
                        j = this.m_int_next[i] > -1 ? this.m_int_next[i] : 0;
                        v_int_violate = 0;  // reset
                    }
                    else if (v_int_violate == 1)
                    {
                        i = j;
                    }
                }
            }
            // Kiểm tra lần cuối, trường hợp duyệt hết

            return this.m_int_position;
        }

        public int SearchAccurate(string ip_str_corpus, string ip_str_pattern, int ip_int_startIndex)
        {
            var k = 0;
            var i = 0;
            var m = ip_int_startIndex;
            var slen = ip_str_corpus.Length;
            var plen = ip_str_pattern.Length;

            this.m_int_position = -1;
            this.m_int_violate = 0;
            this.CreateNextTable(ip_str_pattern);
            while ((k = m + i) < slen)
            {
                if (Char.ToUpper(ip_str_pattern[i]) == Char.ToUpper(ip_str_corpus[k]))
                {
                    if (++i == plen)
                    {
                        // Tìm thấy
                        this.m_int_position = m;
                        break;
                    }
                }
                else
                {
                    m += i - this.m_int_next[i];
                    i = this.m_int_next[i] > -1 ? this.m_int_next[i] : 0;
                }
            }

            return this.m_int_position;
        }


        internal int GetWordNumber(string text)
        {
            MatchCollection collection = Regex.Matches(text, @"[\S]+");
            return collection.Count;
        }
    }
}
